package Solutions;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Classname NumOfLIS
 * @Description TODO
 * @Date 2021/9/20 14:23
 * @Created by ASUS
 * 示例 1:
 * <p>
 * 输入: [1,3,5,4,7]
 * 输出: 2
 * 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
 * <p>
 * 示例 2:
 * <p>
 * 输入: [2,2,2,2,2]
 * 输出: 5
 * 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class NumOfLIS {


    public static void main(String[] args) {
        System.out.println(new NumOfLIS().findNumberOfLIS(new int[]{1, 2, 4, 3, 5, 4, 7, 2}));
    }

    public int findNumberOfLIS(int[] nums) {
        if (nums.length < 2) return nums.length;
        int[] dp = new int[nums.length], cnt = new int[nums.length];
        dp[0] = 1;
        cnt[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            // find the number before that fit and count the cnt
            dp[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] >= nums[i]) continue;
                // nums[j] < nums[i]
                if (dp[j] + 1 > dp[i]) { // find another one longer sequence
                    // update dp[i] to (dp[j] + 1)
                    dp[i] = dp[j] + 1;
                    // reset cnt[i]
                    cnt[i] = cnt[j];
                } else if (dp[j] + 1 == dp[i]) {// 累加方法种类数
                    cnt[i] += cnt[j];
                }
            }
        }
        int res = 0;
        int dp_max = findMax(dp);
        for (int i = dp.length - 1; i >= 0; i--) {
            if (dp[i] == dp_max) res += cnt[i];
        }
        System.out.println(Arrays.toString(dp));
        System.out.println(Arrays.toString(cnt));
        return res;
    }

    private int findMax(int[] dp) {
        int max = dp[0];
        for (int d : dp) max = Math.max(max, d);
        return max;
    }


}
